home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / tex / finds101.zip / BMSEAR.C next >
Text File  |  1986-08-05  |  3KB  |  108 lines
  1. /*
  2.     BMCompile is the part of the Boyer-Moore string search algorithm that
  3.      "compiles" the search string.  Pattern is a pointer to the search string,
  4.      pl is the length, in bytes, of the search string, and d is a pointer to
  5.      a 256 entry integer array to hold the "compiled" string.  It is a
  6.      separate function to allow "compilation" once for many searches such as
  7.      searching the lines of a file.
  8. */
  9. BMCompile (Pattern, pl, d)
  10. char *Pattern;
  11. int pl, d[];
  12. {    
  13.     int i;
  14.  
  15.     for (i=0; i<256; i++) d[i] = pl;
  16.     for (i=0; i<pl-1; i++) d[Pattern[i]] = pl - i - 1;
  17.     }
  18.  
  19. /*
  20.     BMCompile is the part of the Boyer-Moore string search algorithm that
  21.      "compiles" the search string.  Pattern is a pointer to the search string,
  22.      pl is the length, in bytes, of the search string, and d is a pointer to
  23.      a 256 entry integer array to hold the "compiled" string.  It is a
  24.      separate function to allow "compilation" once for many searches such as
  25.      searching the lines of a file.
  26. */
  27. BMCompileI (Pattern, pl, d)
  28. char *Pattern;
  29. int pl, d[];
  30. {    
  31.     int i;
  32.  
  33.     for (i=0; i<256; i++) d[i] = pl;
  34.     for (i=0; i<pl-1; i++) d[toupper(Pattern[i])] = pl - i - 1;
  35.     }
  36.  
  37. /*
  38.     BMSearch is the actual search algorithm for the Boyer-Moore string
  39.      search.  The search string, Pattern, must be "compiled" by BMCompile
  40.      before BMSearch is called.  Line is a pointer to the string to be
  41.      searched and sl is its length in bytes.  Pattern is a pointer to the
  42.      string to search for and pl is its length in bytes.  d is a pointer
  43.      to the 256 entry integer array that contains the "compiled" form of
  44.      Pattern.  BMSearch returns -1 if Pattern is not contained in line and
  45.      the pointer to the first matching character if it is contained in line.
  46.      This version of BMSearch is case sensitive.
  47. */
  48. BMSearch (Line, sl, Pattern, pl, d)
  49. char *Line, *Pattern;
  50. int sl, pl, d[];
  51. {    
  52.     int i, j, k, io;
  53.  
  54.     i = pl; 
  55.     io = 0;
  56.     do {    
  57.         io = i;
  58.         j = pl; 
  59.         k = i;
  60.         do {    
  61.             k--; 
  62.             j--;
  63.             }
  64.         while ((j >= 0) && (Pattern[j] == Line[k]));
  65.         i = i + d[Line[i-1]];
  66.         }
  67.     while ((j >= 0) && (i <= sl));
  68.     if (j < 0) return(io - pl);
  69.     else return(-1);
  70.     }
  71.  
  72. /*
  73.     BMSearch is the actual search algorithm for the Boyer-Moore string
  74.      search.  The search string, Pattern, must be "compiled" by BMCompile
  75.      before BMSearch is called.  Line is a pointer to the string to be
  76.      searched and sl is its length in bytes.  Pattern is a pointer to the
  77.      string to search for and pl is its length in bytes.  d is a pointer
  78.      to the 256 entry integer array that contains the "compiled" form of
  79.      Pattern.  BMSearch returns -1 if Pattern is not contained in line and
  80.      the pointer to the first matching character if it is contained in line.
  81.      This version of BMSearch is case insensitive.
  82. */
  83. BMSearchI (Line, sl, Pattern, pl, d)
  84. char *Line, *Pattern;
  85. int sl, pl, d[];
  86. {    
  87.     int i, j, k, io;
  88.  
  89.     i = pl; 
  90.     io = 0;
  91.     do {    
  92.         io = i;
  93.         j = pl; 
  94.         k = i;
  95.         do {    
  96.             k--; 
  97.             j--;
  98.             }
  99.         while ((j >= 0) && (toupper(Pattern[j]) == toupper(Line[k])));
  100.         i = i + d[toupper(Line[i-1])];
  101.         }
  102.     while ((j >= 0) && (i <= sl));
  103.     if (j < 0) return(io - pl);
  104.     else return(-1);
  105.     }
  106.  
  107.  
  108.